class Solution {
    /*
        存在的问题：
            找中点需要找到位置较小的中点，不然如【1,2】就会一直递归找到中点【2】
    */
    public ListNode sortList(ListNode head) {
        if( head==null || head.next==null )
            return head;
        return mergeSort(head);
    }
    public ListNode mergeSort(ListNode head){
        if( head==null || head.next==null )
            return head;
        // 1、找到前一个中点
        ListNode fast = head , slow = head;
        while( fast!=null && fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2.递归
        ListNode l2 = mergeSort(slow.next);
        slow.next = null;
        ListNode l1 = mergeSort(head);
        return merge(l1,l2);
    }
    public ListNode merge(ListNode l1, ListNode l2) {
        if( l1==null )
            return l2;
        else if(l2==null)
            return l1;
        else if( l1.val<l2.val ){
            l1.next = merge(l1.next,l2);
            return l1;
        }else{
            l2.next = merge(l1,l2.next);
            return l2;
        }
    }
}